package put.io.lists;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * Class used to perform operations on sorted lists of numbers.
 *
 * @author Marcin Szeląg
 */
public class SortedListsOperations {

	/**
	 * Auxiliary method which converts given <code>ArrayList</code> of <code>Integer</code> numbers to array of <code>int</code> numbers
	 * 
	 * @param arrayList array list with <code>Integer</code> numbers
	 * @return array of <code>int</code> numbers
	 */
	public int[] convertArrayList2IntArray(ArrayList<Integer> arrayList) {
		if (arrayList == null)
			return null;

		int arrayListSize = arrayList.size();
		int[] array = new int[arrayListSize];

		for (int i = 0; i < arrayListSize; i++)
			array[i] = (arrayList.get(i)).intValue();
		
		return array;
	}
	
	/**
	 * Checks if given list of numbers is sorted ascendingly, contains no repetitions
	 * and each number is not smaller than zero.
	 * 
	 * @param list checked list of numbers
	 * 
	 * @return <code>true</code> if given list of numbers is valid, <code>false</code> otherwise
	 */
	private boolean validateListOfNumbers(int[] list) {
		//validate list
		int listSize = (list == null) ? 0 : list.length;
		if (listSize > 0 && list[0] < 0)
			return false;
		for (int i = 0; i < listSize; i++)
			//there is also next number at the list
			if (i + 1 < listSize)
				if (list[i] >= list[i + 1])
					return false;

		return true;
	}

	/**
	 * Adds two lists of numbers and returns calculated sum.
	 * If any number is present at both lists, at resulting list it will appear only once.
	 * Very important (checked) requirement is that both lists of numbers must be sorted ascendingly,
	 * with no repetitions (each list element can appear only once) and no negative numbers.
	 * In this case resulting list also will be sorted ascendingly and none of its elements will appear twice.
	 * 
	 * @param list1 first list to add, which should contain ascendingly sorted, non-repeating, and non-negative numbers
	 * @param list2 second list to add, which should contain ascendingly sorted, non-repeating, and non-negative numbers
	 * 
	 * @return ascendingly sorted sum of two given lists of numbers (without repetitions)
	 * 
	 * @throws InvalidValueException when any of input lists is not sorted ascendingly, contains repetitions,
	 *         or contains negative number
	 */
	public int[] addListsOfNumbers(int[] list1, int[] list2) {
		//validate first list
		if (validateListOfNumbers(list1) == false)
			throw new InvalidValueException("First list of numbers must be sorted ascendingly, with no repetitions.");
		//validate second list
		if (validateListOfNumbers(list2) == false)
			throw new InvalidValueException("Second list of numbers must be sorted ascendingly, with no repetitions.");

		int list1Index = 0;
		int list2Index = 0;
		int number1;
		int number2;
		ArrayList<Integer> resultingList = new ArrayList<Integer>();
		
		int list1Length = (list1 == null) ? 0 : list1.length;
		int list2Length = (list2 == null) ? 0 : list2.length;

		boolean continueAdding = true;
		while (continueAdding) {
			//end of first list
			if (list1Index >= list1Length)
				//end of second list
				if (list2Index >= list2Length)
					//finish construction of resulting list
					continueAdding = false;
				//continue with second list
				else
					//add element from second list
					resultingList.add(new Integer(list2[list2Index++]));
			//continue with first list
			else
				//end of second list
				if (list2Index >= list2Length)
					//add element from first list
					resultingList.add(new Integer(list1[list1Index++]));
				//continue with second list
				else {
					number1 = list1[list1Index];
					number2 = list2[list2Index];
					if (number1 < number2) {
						resultingList.add(new Integer(number1));
						list1Index++;
					}
					else if (number1 == number2) {
						resultingList.add(new Integer(number1));
						list1Index++;
						list2Index++;
					}
					//(number2 < number1)
					else {
						resultingList.add(new Integer(number2));
						list2Index++;
					}
				}
		}

		return convertArrayList2IntArray(resultingList);
	}
	
	/**
	 * Subtracts two lists of numbers and returns calculated difference.
	 * Very important (checked) requirement is that both lists of numbers must be sorted ascendingly,
	 * with no repetitions (each list element can appear only once) and no negative numbers.
	 * In this case resulting list also will be sorted ascendingly and none of its elements will appear twice.
	 * 
	 * @param list1 first list, which should contain ascendingly sorted, non-repeating, and non-negative numbers
	 * @param list2 second list, subtracted from first, which should contain ascendingly sorted, non-repeating, and non-negative numbers
	 * 
	 * @return ascendingly sorted difference of two given lists of numbers (without repetitions)
	 * 
	 * @throws InvalidValueException when any of input lists is not sorted ascendingly, contains repetitions
	 *         or contains negative number
	 */
	public int[] subtractListsOfNumbers(int[] list1, int[] list2) {
		//validate first list
		if (validateListOfNumbers(list1) == false)
			throw new InvalidValueException("First list of numbers must be sorted ascendingly, with no repetitions.");
		//validate second list
		if (validateListOfNumbers(list2) == false)
			throw new InvalidValueException("Second list of numbers must be sorted ascendingly, with no repetitions.");

		int list2Index = 0;
		int number1;
		int number2;

		boolean addNumber1;
		ArrayList<Integer> resultingList = new ArrayList<Integer>();
		
		int list1Length = (list1 == null) ? 0 : list1.length;
		int list2Length = (list2 == null) ? 0 : list2.length;

		for (int i = 0; i < list1Length; i++) {
			number1 = list1[i];
			//initially assume that number1 should be added to the resulting list
			addNumber1 = true;

			//search until number2 is equal or greater than number1
			for (int j = list2Index; j < list2Length; j++) {
				number2 = list2[j];

				//number1 should not be added to the resulting list
				if (number1 == number2) {
					list2Index = j + 1;
					addNumber1 = false;
					break;
				}
				//number1 should be added to the resulting list
				else if (number1 < number2) {
					list2Index = j;
					break;
				}
			}
			
			if (addNumber1)
				resultingList.add(new Integer(number1));				
		}
		
		return convertArrayList2IntArray(resultingList);
	}
	
	/**
	 * Checks if given ascendingly sorted list of integer non-negative numbers contains given number.
	 * Uses binary search. Because of efficiency, given list is not validated.
	 * It must be sorted ascendingly in order to avoid undefined results.
	 * 
	 * @param list list of numbers that should be checked
	 * @param number number searched in the given list
	 * 
	 * @return <code>true</code> if given list contains given number, <code>false</code> otherwise
	 */
	public boolean listOfNumbersContainsNumber(int[] list, int number) {
		if (list == null || list.length == 0)
			return false;
		
		if (Arrays.binarySearch(list, number) >= 0) //binary search of given array of integers, sorted ascendingly
			return true;
		else
			return false;
	}

	/**
	 * Sole constructor.
	 */
	public SortedListsOperations() {}
	
}
